# -*- coding: utf-8 -*-
from structures.hashtable import HashTable
from structures.list import List
from structures.heap import Heap
from structures.unionfind import UnionFind
from graphs.graph import *


class MatrixGraph(Graph):

    def __init__(self):
        self.__adjacency = []
        self.__vertices = HashTable()

    def add_vertex(self, name):
        self.__vertices[name] = self.__length()
        self.__adjacency.append([None] * self.__length())
        for i in range(self.__length()):
            self.__adjacency[i].append(None)

    def add_edge(self, source, dest, weight):
        edge = [source, dest, weight]
        indexsource = self.__vertices[source]
        indexdest = self.__vertices[dest]
        if indexsource is not None and indexdest is not None:
            self.__adjacency[indexsource][indexdest] = edge
        else:
            name = source
            if indexdest is None:
                name = dest
            raise Exception("Vertex '" + name + "' doesn't exist")

    def vertex_count(self):
        return self.__length()

    def edge_count(self):
        count = 0
        length = self.__length() - 1

        for i in range(length):
            for j in range(length):
                if self.__adjacency[i][j] is not None:
                    count += 1

        return count

    def get_edge(self, source, dest):
        indexsource = self.__vertices[source]
        indexdest = self.__vertices[dest]
        return self.__adjacency[indexsource][indexdest][2]

    def __length(self):
        return len(self.__adjacency)

    def run_dijkstra(self, source, distance):
        if self.__vertices[source] is None:
            raise Exception('Source vertex does not exist!')

        # Stores the name of the previous node for the key
        previous = HashTable()
        # Stores the calculated cost so far for each node
        # from the source
        cost = HashTable()
        # Prority Queue
        heap = Heap()
        # Represents the value infinity
        infinity = float("inf")
        # Initialize all costs to infinity
        for name in self.__vertices.get_keys():
            cost[name] = infinity
        # Set cost to source node to zero
        # and add to heap
        cost[source] = 0
        heap.insert(cost[source], source)
        # Count how many nodes have been added to S so far
        count = 0
        # While there are nodes missing
        # and the heap is not empty (this condition is added
        # in case the graph is not connected)
        while count < self.vertex_count() and not heap.empty():
            name = heap.extract_min()
            count += 1
            # Get index for vertex in matrix
            index = self.__vertices[name]
            # Look for adjacent nodes
            for i in range(self.__length()):
                edge = self.__adjacency[index][i]
                if edge is not None:
                    # Calculate new cost
                    weight = edge[2]
                    dest = edge[1]
                    newcost = cost[name] + weight
                    # Update cost if it's smaller and is not in S
                    if newcost < cost[dest]:
                        cost[dest] = newcost
                        previous[dest] = name
                        heap.insert(newcost, dest)

        # Get all vertex that are at least distance
        # from source
        actors = List()
        for name in self.__vertices.get_keys():
            if distance <= cost[name]:
                actors.add(name)

        return actors

    def to_string(self):
        output = ''
        for i in range(self.__length()):
            output += self.__vertices.get_keys()[i] + ': '
            for j in range(self.__length()):
                edge = self.__adjacency[i][j]
                destination = edge[1]
                weight = edge[2]
                if edge is not None:
                    output += '(' + destination + ', '
                    output += str(weight) + ') '
            output += '\n'
        return output

    def load(self, filename):
        file = open(filename)
        adj = HashTable()

        for line in file:
            pair = line.split(Graph.NAME_SEPARATOR)
            name = pair[0].strip()
            adjlist = pair[1].strip()
            self.add_vertex(name)
            adj[name] = adjlist

        for name in self.__vertices.get_keys():
            list = adj[name]
            edges = list.split(Graph.ADJ_LIST_SEPARATOR)
            for edge in edges:
                edge = edge.strip()
                if len(edge) > 0:
                    words = edge.split(Graph.WEIGHT_SEPARATOR)
                    destIndex = int(words[0].strip())
                    dest = self.__vertices.get_key(destIndex)
                    weight = None
                    weight = int(words[1])
                    self.add_edge(name, dest, weight)

        file.close()
